package test.LeetCode;


import test.entity.ListNode;

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    // [2279. 装满石头的背包的最大数量](https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks/)
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        for (int i = 0; i < capacity.length; i++) {
            capacity[i] = capacity[i] - rocks[i];
        }
        int count = 0;
        Arrays.sort(capacity);
        for (int i = 0; i < capacity.length; i++) {
            if (additionalRocks == 0) {
                break;
            }
            // 如果减的过来则count++;
            if (additionalRocks >= capacity[i]) {
                additionalRocks -= capacity[i];
                count++;
                continue;
            }
            break;
        }
        return count;
    }

    // [5.最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/)
    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        char[] arr = s.toCharArray();
        int maxIndex = 0, maxLen = 0;
        for (int i = 0; i <s.length(); i++) {
            int count = 1;
            int left = i, right = i;
            while (left >= 0 && right < s.length() && arr[left] == arr[right]) {
                if (left == right){
                    left--;right++;
                    continue;
                }
                count+=2;
                if (count > maxLen){
                    maxLen = count;
                    maxIndex = i;
                }
                left--;right++;
            }
        }
        for (int i = 0; i <s.length()-1; i++) {
            int count = 2;
            int left = i, right = i+1;
            while (left >=0 && right < s.length() && arr[left] == arr[right]) {
                if (left+1 == right){
                    left--;right++;
                    if (maxLen<count){
                        maxLen = count;
                        maxIndex = i;
                    }
                    continue;
                }
                count+=2;
                if (count > maxLen){
                    maxLen = count;
                    maxIndex = i;
                }
                left--;right++;
            }
        }
        if (maxLen==0&&maxIndex==0){
            return String.valueOf(arr[0]);
        }
        System.out.println(maxIndex);
        System.out.println(maxLen);
        return maxLen%2==1?s.substring(maxIndex-maxLen/2,maxIndex+maxLen/2+1):s.substring(maxIndex-(maxLen-2)/2,maxIndex+(maxLen-2)/2+2);
    }

    // [45.最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/)
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 0; i < nums.length; i++)
            for (int j = 0; j < i; j++)
                if (nums[i]>nums[j])
                    dp[i] = Math.max(dp[i],dp[j]+1);
        return Arrays.stream(dp).max().getAsInt();
    }
    // 链表排序
    /*public ListNode sortList(ListNode head) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        while (head!=null){
            map.put(head.val,head);
            head = head.next;
        }

    }*/
    public ListNode sortList1(ListNode head) {
        int i = 0;
        ArrayList<ListNode> list = new ArrayList<>();
        while (head!=null){
            list.add(head);
            head = head.next;
        }
        list.sort((a,b)->a.val-b.val);
        for (int j = 0; j < list.size(); j++) {
            ListNode node = list.get(j);
            if (j==list.size()-1){
                node.next = null;
            }
            node.next = list.get(j+1);
        }
        return list.get(0);
    }

    public static String longestCommonPrefix(String[] strs) {
        int min = strs[0].length();
        for(int j=0;j<strs.length;j++){
            min = Math.min(strs[j].length(),min);
        }
        char[] list = new char[min];
        for(int j=0;j<min;j++){
            for(int i=0;i<strs.length;i++){
                char temp = strs[i].charAt(j);
                if(list[j] != 0){
                    if(list[j]!=temp) {
                        list[j] = 0;
                        return new String(list).trim();
                    }
                }else{
                    list[j] = temp;
                }
            }
        }
        return new String(list).trim();
    }
    


    public static void main(String[] args) {
//        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"}));
        String s = new String(new char[]{'a', 'b', 'c',' '}).trim();
        System.out.println(s);
    }
}